Sort

发表于 | 分类于 |

快排最重要的就是 partition 函数，i 记录第一个不小于 pivot 的位置：

  1. 取数组中最后一个数字为 pivot，同时用 i 记录第一个位置；
  2. 遍历数组，比较每个数和 pivot；
  3. 数组内的值小于 pivot 时，进入循环；
  4. 保证 i 是第一个不小于 pivot 的位置；
  5. i == j, i ++
  6. i != j, 交换数组中 i 和 j，且 i++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Arrays;

public class myQuickSort {
    public static void quickSort(int[] nums, int size) {
        quickSortIner(nums, 0, size - 1);
    }

    public static void quickSortIner(int[] nums, int start, int end) {
        if (start >= end) return;

        int pivot = partition(nums, start, end);
        quickSortIner(nums, start, pivot - 1);
        quickSortIner(nums, pivot + 1, end);
    }

    // i 是用来记录第一个比 pivot 大的数的位置
    private static int partition(int[] nums, int start, int end) {
        int pivot = nums[end];
        int i = start;
        for (int j = start; j < end; j++) {
            if (nums[j] < pivot) {
                int tmp = nums[i];
                nums[i++] = nums[j];
                nums[j] = tmp;
            }
        }

        nums[end] = nums[i];
        nums[i] = pivot;

        return i;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 1, 3, 8, 5};
        quickSort(nums, 5);
        System.out.println(Arrays.toString(nums));
    }
}